\documentclass[a4paper]{scrartcl}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{graphicx}
\usepackage{color}
\newcommand{\A}{\mathcal{A}}
\newcommand{\F}{\mathcal{F}}
\renewcommand{\P}{\mathcal{P}}
\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\newcommand{\todo}[1]{\noindent\textbf{TODO: }\marginpar{****}%
\textit{\red{{#1}}}\textbf{ :ODOT}}%

\begin{document}
%  \date{}
\section{Model}

We consider a network of $k$ distinct processes $\P = \{p_1,\dots,p_k\}$ 
that are
pairwise connected by bidirectional point-to-point communication links.
Each process executes an instance of a distributed algorithm $\A$.
The computation of $\A$ advances in synchronous rounds where, in each round,
every node can perform local computation and send a message of $B$ bits over
each incident communication link, which is guaranteed to be received before the
start of the next round.
Note that processes have no other means of communication and
do not share any memory.

An \emph{input domain} $\F$ is a family of simple undirected graphs of $n$
vertices for some $n\ge k$; we are mostly interested in the case where $n 
\gg k$.
Depending on the problem at hand, we assume that vertices and/or edges
of the graphs in $\F$ are labeled with integers chosen from a set of size at most
polynomial in $n$.
For example, for the random walk problem, we assume that the vertices of 
graphs in $\F$ have unique ids chosen from $[1,n^2]$.
Initially, we associate an input with every process that we determine as
 follows:
For a given graph $G \in \F$, we consider a partitioning of $V(G)$ into
$V_1,\dots,V_k$ where $|V_i| \in \tilde{\Theta}(n/k)$, for $1 \le i \le 
k$.
This yields a map $\Phi : V(G) \rightarrow \P$ that maps each vertex of $G$ to
some process.
For each $p_i \in \P$, the \emph{input of the algorithm at $p_i$} consists 
of
the induced graph $G[V_i]$ and the set $\{(u,\Phi(u)) \mid \exists v \in 
  V_i\colon
(u,v) \in E(G) \}$.
Note that process $p_i$ has no knowledge of the actual partitioning and, in particular,
does not know the mapping $\Phi(v)$ of any vertex $v \notin V_i$, unless 
$v$ is adjacent to some $u \in V_i$.

We say that $\A$ terminates in round $r$ if all processes have reached a 
terminal state.
The \emph{time complexity of $\A$} is the maximum number of rounds until 
termination, over all graphs in $\F$.
Note that we consider local computation to happen instantaneously, which 
is motivated by the fact that inter-process communication is much more 
taxing than computation and communication taking place within the same 
process.
%That is, if $v$ is adjacent to some $u \in V_i$, then the mapping 
%$p_j=\Phi(v)$ reveals the process $p_j$ to which $v$ has been assigned.

It is instructive to consider the special case of $k=n$ and $\Phi$ being one-to-one.
This corresponds exactly to a distributed network of $n$ nodes where the
communication links are a superset of the edges of the input graph $G$.  
In this case, initially each process only knows a port numbering of its 
communication links, but it does not know the actual vertices of $G$ that 
are assigned to the processes at the endpoints of its links.

\end{document}
